import common.TreeNode;

import java.util.ArrayList;
import java.util.List;

public class pathSum {
    /**
     * 解决方案类，用于寻找二叉树中所有从根节点到叶子节点的路径，其路径上的元素之和等于给定的目标和
     */
    public class Solution {
        /**
         * 寻找二叉树中所有路径和等于目标和的路径
         *
         * @param root 二叉树的根节点
         * @param targetSum 目标和
         * @return 所有满足路径和等于目标和的路径列表
         */
        public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
            // 存储所有满足条件的路径
            List<List<Integer>> ans = new ArrayList<>();
            // 存储当前遍历的路径
            List<Integer> path = new ArrayList<>();
            // 调用深度优先搜索函数
            dfs(root, targetSum, path, ans);
            return ans;
        }

        /**
         * 深度优先搜索函数，用于递归地寻找所有路径
         *
         * @param root 当前节点
         * @param targetSum 当前目标和
         * @param path 当前路径
         * @param ans 存储所有满足条件的路径
         */
        void dfs(TreeNode root, int targetSum, List<Integer> path, List<List<Integer>> ans){
            // 如果当前节点为空，则返回
            if(root == null) return;
            // 将当前节点的值添加到路径中
            path.add(root.val);
            // 从目标和中减去当前节点的值
            targetSum -= root.val;
            // 如果当前节点是叶子节点且目标和为0，说明找到了一条满足条件的路径
            if(root.left == root.right && targetSum == 0){
                // 将当前路径添加到结果集中
                ans.add(new ArrayList<>(path));
            }else{
                // 递归遍历左子树
                dfs(root.left, targetSum, path, ans);
                // 递归遍历右子树
                dfs(root.right, targetSum, path, ans);
            }
            // 回溯，从当前路径中移除最后一个元素
            path.remove(path.size()-1);
        }
    }

}
